import java.util.HashMap;
import java.util.Map;

public class BuildTreeWithPreAndInOrder {

    private int[] inorder;
    private int[] preorder;
    private Map<Integer, Integer> position

            = new HashMap<>();
    private int preIndex = 0;

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        this.preorder = preorder;
        this.inorder = inorder;
        for (int i = 0; i < inorder.length; i++) {
            position.put(inorder[i], i);
        }

        return helper(0, preorder.length);

    }

    private TreeNode helper(int left, int right) {

        if (left >= right) return null;
        int val = preorder[preIndex];
        Integer mid = position.get(val);
        preIndex++;
        TreeNode root = new TreeNode(val);
        root.left = helper(left, mid);
        root.right = helper(mid + 1, right);
        return root;


    }

}
